// Time:  O(n)
// Space: O(1)

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string customSortString(string order, string s) {
        if(s.empty()){
            return "";
        }

        vector<int> count(26, 0);
        for(const char& c: s) {
            ++count[c - 'a'];
        }

        string result;
        result.reserve(s.length());

        for(const char& c: order) {
            result.append(count[c - 'a'], c);
            count[c - 'a'] = 0;
        }

        for(char c = 'a'; c <= 'z'; ++c) {
            result.append(count[c - 'a'], c);
        }
        return result;
    }
};
